#include<stdio.h>
#include<stdlib.h>

typedef struct Node
{
	char data;
	struct Node *next;
}Node;

//初始化
void InitList(Node* &L)
{
	L=(Node*)malloc(sizeof(Node));
	L->next=NULL;
}

//销毁
void DestroyList(Node* L)
{
	Node*p,*pre;
	pre=L;
	p=L->next;
	while(p!=NULL)
	{
		free(pre);
		pre=p;
		p=pre->next;
	}
	free(pre);
}

//判空
bool ListEmpty(Node* L)
{
	return L->next==NULL;
}

//求长
int ListLenght(Node* L)
{
	Node* p=L;
	int n=0;
	while(p->next!=NULL)
	{
		p=p->next;
		n++;
	}
	return n;
}

//输出
void DispList(Node* L)
{
	Node*p=L->next;
	while(p!=NULL)
	{
		printf("%c ",p->data);
		p=p->next;
	}
	printf("\n");
}

//获取
bool GetElem(Node* L,int i,char &e)
{
	if(i<=0||i>ListLenght(L))
		return false;
	int j=0;
	Node*p=L;
	while(j<i&&p!=NULL)
	{
		p=p->next;
		j++;
	}
	if(p==NULL)
		return false;
	else
	{
		e=p->data;
		return true;
	}
}

//查找
int LocateElem(Node* L,char e)
{
	int j=0;
	Node*p=L->next;
	while(p!=NULL)
	{
		if(p->data==e)
			return j+1;
		p=p->next;
	}
	return 0;
}

//插入
bool ListInsert(Node* &L,int i,char e)
{
	if(i<=0)
		return false;
	int j=0;
	Node*p=L;
	Node*s;
	while(j<i-1&&p!=NULL)
	{
		p=p->next;
		j++;
	}
	if(p==NULL)
		return false;
	else
	{
		s=(Node*)malloc(sizeof(Node));
		s->data=e;
		s->next=p->next;
		p->next=s;
		return true;
	}
}

//删除
bool ListDelete(Node* &L,int i ,char &e)
{
	if(i<=0||i>ListLenght(L))
		return false;
	int j=0;
	Node*p=L,*q;
	while(j<i-1&&p!=NULL)
	{
		p=p->next;
		j++;
	}
	if(p==NULL)
		return false;
	else
	{
		q=p->next;
		if(q==NULL)
			return false;
		e=q->data;
		p->next=q->next;
		free(q);
		return true;
	}
}

int main()
{
	Node*h;
	char e;
	InitList(h);
	ListInsert(h,1,'a');
	ListInsert(h,2,'b');
	ListInsert(h,3,'c');
	ListInsert(h,4,'d');
	ListInsert(h,5,'e');
	DispList(h);
	printf("长度：%d\n",ListLenght(h));
	printf("链表%s\n",(ListEmpty(h)?"空":"非空"));
	GetElem(h,3,e);
	printf("第3个元素为%c\n",e);
	printf("元素a的位置为第%d\n",LocateElem(h,'a'));
	ListInsert(h,4,'f');
	DispList(h);
	ListDelete(h,3,e);
	DispList(h);
	DestroyList(h);
}
